package com.example.demo.lc.dfs;
/**
* @author wzh
* @date 2021/8/10 10:32 上午
* @Description 深度遍历｜回溯
 * https://leetcode-cn.com/problems/word-search/
*/
public class LeetCode79 {
    public static void main(String[] args) {
        //egg1
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        //String word = "ABCCED";
        //egg2
        //String word = "SEE";
        //egg3
        String word = "ABCD";
        System.out.println(exist(board,word));
    }

    public static boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean flag = check(board,visited,i,j,word,0);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int s) {
        if(board[i][j] != word.charAt(s)){
            return false;
        }else if(word.length()-1 == s){
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};  //方向-上下左右
        boolean result = false;
        for (int[] direction : directions) {
            int m = i+direction[0];
            int n = j+direction[1];
            if(m>=0 && n>=0 && m<board.length && n<board[0].length){
                if(!visited[m][n]){
                    boolean check = check(board, visited, m, n, word, s+1);
                    if(check){
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}
